//bool canJump(int* nums, int numsSize) 
//{
//    if (numsSize <= 1)return true;
//    int i = 0, sum = nums[0];
//   
//    while (i < (numsSize - 1))
//    {
//        while (sum)
//        {
//            if (sum + i >= numsSize - 1)
//                return true;       
//            i++;               
//            sum--;               
//            if (nums[i] > sum)    
//            {
//                sum = nums[i];
//            }
//        }                      
//        return false;
//    }
//    return false;
//}




//int uniquePaths(int m, int n) 
//{
//    int f[m][n];
//    for (int i = 0; i < m; ++i) 
//    {
//        f[i][0] = 1;
//    }
//    for (int j = 0; j < n; ++j)
//    {
//        f[0][j] = 1;
//    }
//    for (int i = 1; i < m; ++i) 
//    {
//        for (int j = 1; j < n; ++j) 
//        {
//            f[i][j] = f[i - 1][j] + f[i][j - 1];
//        }
//    }
//    return f[m - 1][n - 1];
//}




//int min_fun(int a, int b)
//{
//    int c = a < b ? a : b;
//    return c;
//}
//
//int coinChange(int* coins, int coinsSize, int amount)
//{
//    int f[amount + 1];
//    f[0] = 0;
//
//    for (int i = 1; i <= amount; i++)
//    {
//        f[i] = INT_MAX;
//        for (int j = 0; j < coinsSize; j++)
//        {
//            if (i >= coins[j] && f[i - coins[j]] != INT_MAX)
//            {
//                f[i] = min_fun(f[i], f[i - coins[j]] + 1);
//            }
//        }
//    }
//    if (f[amount] == INT_MAX)
//        f[amount] = -1;
//
//    return f[amount];
//
//}



//
//class Solution
//{
//    int dfs(int i, vector<int>& nums)
//    {
//        int n = nums.size();
//        int ret = 1; 
//        
//        for (int j = i + 1; j < n; j++)
//        {
//            if (nums[j] > nums[i])
//            {
//                ret = max(ret, 1 + dfs(j, nums));
//            }
//        }
//        return ret;
//    }
//
//public:
//    int lengthOfLIS(vector<int>& nums)
//    {
//        int ret = 0;
//        int n = nums.size();
//        for (int i = 0; i < n; i++)
//        {
//            ret = max(ret, dfs(i, nums));
//        }
//        return ret;
//    }
//};





//
//
//class Solution
//{
//public:
//    int lengthOfLIS(vector<int>& nums)
//    {
//        int n = nums.size();
//        int ret = 1;
//        vector<int> dp(n, 1);
//        for (int i = n - 2; i >= 0; i--)
//        {
//            for (int j = i + 1; j < n; j++)
//            {
//                if (nums[j] > nums[i])
//                {
//                    dp[i] = max(1 + dp[j], dp[i]);
//                }
//            }
//            ret = max(ret, dp[i]);
//        }
//        return ret;
//    }
//};





class Solution
{
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        int ret = 1;
        vector<int> dp(n, 1);

        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] > nums[j])
                {
                    dp[i] = max(dp[i], 1 + dp[j]);
                }
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

